import re


def LCS(x, y):
    import numpy as np
    c = np.zeros((len(x) + 1, len(y) + 1))
    b = np.zeros((len(x) + 1, len(y) + 1))
    for i in range(1, len(x) + 1):
        for j in range(1, len(y) + 1):
            if x[i - 1] == y[j - 1]:
                c[i, j] = c[i - 1, j - 1] + 1
                b[i, j] = 2
            else:
                if c[i - 1, j] >= c[i, j - 1]:
                    c[i, j] = c[i - 1, j]
                    b[i, j] = 1
                else:
                    c[i, j] = c[i, j - 1]
                    b[i, j] = 3
    return c, b


def getLCS(x, y):
    c, b = LCS(x, y)
    i = len(x)
    j = len(y)
    lcs = ''
    while i > 0 and j > 0:
        if b[i][j] == 2:
            lcs = x[i - 1] + lcs
            i -= 1
            j -= 1
        if b[i][j] == 1:
            i -= 1
        if b[i][j] == 3:
            j -= 1
        if b[i][j] == 0:
            break
    return lcs


def isLCS(x, y):
    if x is None or y is None:
        return False
    x = re.sub("[^A-Za-z0-9]", "", x).upper()
    y = re.sub("[^A-Za-z0-9]", "", y).upper()
    z = getLCS(x, y)
    if len(z) == len(x) or len(z) == len(y):
        return True
    else:
        return False

